package offer2

/**
原题链接:
https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/description/?favorite=xb9nqhhg

吴师兄动画
剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：
输入：board = [
	["A","B","C","E"],
	["S","F","C","S"],
	["A","D","E","E"]
],

word = "ABCCED"
 * 输出：true
*/

func exist(board [][]byte, word string) bool {
	//1.获取矩阵的行数, 列数
	row := len(board)
	col := len(board[0])

	//2.声明匿名函数
	var dfs func(i, j, k int) bool

	//参1:行 参2:列 参3:当前字符在目标字符串中的下标
	dfs = func(i, j, k int) bool {
		//如果行或列已经超过范围 或者 单元格的值和字符串的k下标字符不相同,直接返回false
		if i < 0 || i >= row || j < 0 || j >= col || board[i][j] != word[k] {
			return false
		}
		//如果k的长度已经和字符串长度相等,证明已经找到了条件路径
		if k == len(word)-1 {
			return true
		}

		//如果长度没有达到目标字符串的长度,说明需要继续向下找,先将当前位置标记为'#'特殊字符
		board[i][j] = '#'
		//递归调用当前单元格的上下左右位置, 只要有一个满足条件即可
		res := dfs(i+1, j, k+1) ||
			dfs(i-1, j, k+1) ||
			dfs(i, j+1, k+1) ||
			dfs(i, j-1, k+1)

		//将当前单元格的值复原
		board[i][j] = word[k]
		return res
	}

	//3.从每个矩阵的每个位置出发, 一旦遇到能够拼接出字符串的路径, 就返回true
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}
	return false
}
